Many medium-access control (MAC) protocols have been developed for wireless networks. The carrier-sense multiple access (CSMA) protocol was the first to be used in multihop packet-radio networks. A limitation of CSMA in multihop networks is that sources hidden from one another cannot detect their transmissions, which degrades CSMA's performance to that of the pure ALOHA protocol. Many MAC protocols have been proposed and implemented to solve the hidden-terminal problems of CSMA. The throughput of CSMA protocols is very good, as long as the multiple transmitters within range of the same receivers can sense one another's transmissions. Unfortunately, “hidden terminal” problems degrade the performance of CSMA substantially, because carrier sensing cannot prevent collisions in that case.
The busy tone multiple access (BTMA) protocol (F. A. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part II—the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution,” IEEE Trans. Commun., vol. COM-23, no. 12, pp. 1417-1433, 1975.) was the first proposal to combat the hidden-terminal problems of CSMA. BTMA is designed for station-based networks and divides the channel into a message channel and the busy-tone channel. The base station transmits a busy-tone signal on the busy-tone channel as long as it senses carrier on the data channel. Because the base station is in line of sight of all terminals, each terminal can sense the busy-tone channel to determine the state of the data channel. The limitations of BTMA are the use of a separate channel to convey the state of the data channel, the need for the receiver to transmit the busy tone while detecting carrier in the data channel, and the difficulty of detecting the busy-tone signal in a narrow-band channel.
A receiver initiated busy-tone multiple access protocol for packet-radio networks has also been proposed (C. Wu and V. O. K. Li, “Receiver-initiated busy-tone multiple access in packet radio networks,” ACM SIGCOMM 87 Workshop: Frontiers in Computer Communications Technology, Stowe, Vt., USA, 11-13 Aug. 1987). In this scheme, the sender transmits a request-to-send (RTS) to the receiver, before sending a data packet. When the receiver obtains a correct RTS, it transmits a busy tone in a separate channel to alert other sources that they should back off. The correct source is always notified that it can proceed with transmission of the data packet. The limitations of this scheme are that it still requires a separate busy-tone channel and full-duplex operation at the receiver.
Several protocols have been proposed based on different types of “collision-avoidance” handshakes done with small control packets and meant to avoid data collisions when sources of data packets cannot hear one another. The collision-avoidance approach in the prior art follows the basic philosophy first introduced by Tobagi and Kleinrock in the Split-Channel Reservation Multiple Access (SRMA) protocol (F. A. Tobagi and L. Kleinrock, “Packet switching in radio channels: Part III—polling and (dynamic) split-channel reservation multiple access,” IEEE Trans. Commun., vol. COM-24, no. 8, pp. 832-845, 1976). In SRMA, and most subsequent collision-avoidance protocols, a sender node sends a request-to-send (RTS) packet to the intended receiver, either sensing the channel before sending the RTS or not sensing the channel before the RTS transmission. A receiver that hears a clean RTS responds with a clear-to-send (CTS), and the sender can send a data packet after hearing a clean CTS.
U.S. Pat. No. 5,319,641 assigned to Echelon Systems Corp. discloses a method to improve CSMA p-persistent protocols by introducing a random waiting time that stations must wait listening to the channel once they have packets to send. The method disclosed does not work in networks with hidden terminals.
U.S. Pat. No. 4,661,902 assigned to Apple Computer, Inc. discloses a method that amounts to an implementation of SRMA over a single channel in which stations use carrier sensing before sending RTSs.
MACA (P. Karn, “MACA—a new channel access method for packet radio,” in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134-40, ARRL, 1990) consists of a technique that amounts to SRMA running over a single channel in which a request-to-send (RTS) packet is sent without carrier sensing. There appears to be no description of how to support packet trains.
U.S. Pat. No. 5,231,634 assigned to Proxim, Inc. discloses a method that also applies SRMA's basic approach over a single channel. The RTS specifies the length of the impending data packet.
U.S. Pat. No. 5,502,724 assigned to International Business Machines Corporation discloses a method that extends the collision avoidance handshake to allow for multiple data packets to flow among a pair of communicating stations. A station that intends to establish a connection with a second station senses the channel. If the channel is idle, it sends a connection request (CR) packet to the intended receiver station. The CR specifies the number of data packets that the connection includes. The intended receiver sends a connection confirm (CC) packet to the sending station; the CC also specifies the number of packet in the connection. After the exchange of correct CR and CC packets, the sending station may send one or multiple data packets and the receiving station may send an acknowledgment packet specifying which data packets were received correctly. To end the connection, the sending station sends a disconnect request (DR) and the receiving station issues a disconnect confirm (DC). Stations that receive a CR packet back off for an amount of time that is long enough for the advertised number of data packets to be sent to the receiver. After receiving a CR or CC, a station can attempt to access the channel when a timer proportional to the number of packets to be sent in the connection expire, or when it receives a DR or DC packet. The limitation with the method disclosed in U.S. Pat. No. 5,502,724 is that the method cannot ensure collision-fee transmissions of data packets, even with the transmission of CC packets by the receiver. The need for feedback from the receiver to its neighbors on a packet-by-packet basis was demonstrated by Fullmer and Garcia-Luna-Aceves (C. L. Fullmer and J. J. Garcia-Luna-Aceves, “Solutions to Hidden Terminal Problems in Wireless Networks”, Proc. ACM SIGCOMM 97, Cannes, France, Sep. 14-18, 1997). Because the CC packet sent by the receiver may collide with another packet at a neighbor of a receiver, the CC packet does not provide sufficient feedback to hidden nodes; furthermore, the need for feedback packets to be longer than request packets was also demonstrated by Fullmer and Garcia-Luna-Aceves (C. L. Fullmer and J. J. Garcia-Luna-Aceves, “Floor Acquisition Multiple Access (FAMA) for Packet-Radio Networks,” Proc. ACM SIGCOMM 95, Cambridge, Mass., Aug. 28-Sep. 1, 1995). In addition, even though the disclosed method makes reference to broadcast packets sent to all the neighbors of a station, it provides no provisions to ensure that broadcast or multicast packets are received without interference by all the neighbors of a sending station.
U.S. Pat. No. 5,721,725 assigned to Xerox Corp. discloses a method similar to SRMA, and describes it to be an improvement over MACA. The method disclosed extends MACA by specifying in the RTS packets the desired data rate for data packets and allowing sender and receiver to negotiate the transmission data rate. This method fails to guarantee collision free transmissions in networks with hidden terminals because no provisions are made on the length of the CTS being longer than the length of any RTS to ensure that collisions of RTSs and CTSs are detected by hidden stations.
DFWMAC IEEE802.11 (K. C. Chen, “Medium Access Control of Wireless LANs for Mobile Computing,” IEEE Network, vol. 8, no. 5, pp. 50-63, 1994), FAMA-NCS (C. L. Fullmer and J. J. Garcia-Luna-Aceves, “Solutions to Hidden Terminal Problems in Wireless Networks”, Proc. ACM SIGCOMM 97, Cannes, France, Sep. 14-18, 1997), and RIMA (J. J. Garcia-Luna-Aceves and A. Tzamaloukas, “Reversing the Collision Avoidance Handshake in Wireless networks,” Proc. ACM/IEEE Mobicom 99, August 1999) are three recent additional examples of collision-avoidance protocols. IEEE 802.11 is a method very similar to SRMA with carrier sensing for the transmission of RTSs. The objective of FAMA-NCS is for a station that has data to send to acquire control of the channel in the vicinity of the receiver (which we call “the floor”) before sending any data packet, and to ensure that no data packet collides with any other packet at the receiver. FAMA-NCS makes the length of CTSs much longer than the length of RTSs in order to detect the collision of RTSs with CTSs, which cannot be enforced in prior collision-avoidance protocols. RIMA consists of a family of protocols that reverse the collision-avoidance handshake method first introduced in SRMA and makes the receiver polls the sender of data.
Several other medium access control (MAC) protocols have been proposed for either single-channel wireless networks or wireline local area networks that are based on similar RTS-CTS exchanges, or based on RTSs followed by pauses. However, despite the popularity gained by collision-avoidance protocols and systems based on such protocols over the past few years, two key performance limitations of all collision-avoidance MAC protocols are that: (a) they cannot provide channel-access delay guarantees, which represents a big problem for real-time applications; and (b) they lack explicit support of collision-free multicasting or broadcasting, which implies that either a node must transmit the same multicast packet multiple times, once to each multicast-group neighbor, or packets are sent with likelihood of reception as low as the ALOHA protocol. In addition, collision-avoidance protocols require carrier sensing, which is not technically or economically feasible to implement correctly in direct sequence spread spectrum radios with very high chip rates.
To circumvent hidden-terminal interference problems, unique codes (spreading codes or frequency-hopping sequences) can be assigned to receivers or senders. An example of this approach is the Metricom network. However, receiver oriented code assignment (ROCA) and transmitter oriented code assignment (TOCA) require either pre-configuring radios with the node to code mappings, or finding the codes being used by neighboring transmitters or receivers. Furthermore, efficient broadcasting is not guaranteed simply by establishing a TOCA approach, because all the neighbors of a transmitter must agree to listen to the transmitter at the same time to minimize the number of transmissions.
Another approach to channel access used in multihop wireless networks consists of establishing transmission schedules, i.e., allocating stations to different times and data channels (e.g., frequencies, spreading codes, or their combination) in a way that no collisions occur. Transmission scheduling can be static or dynamic; MAC protocols based on dynamic transmission scheduling explore the spatial reuse of the radio channel and thus have much higher channel utilization than such fixed scheduling approaches as TDMA and FDMA.
In TDMA protocols, time is divided into frames consisting of time slots. Time slots are allocated to specific nodes or a centralized station is used to allocate the time slots. The limitations of TDMA stem from the fixed assignment of time slots to nodes, which is slow to adapt to network changes and makes inefficient use of the channel if nodes are bursty sources of traffic, and the use of centralized assignments.
There are many approaches in the prior art based on dynamic TDMA methods in which stations use ALOHA, slotted ALOHA or other contention protocols in an uplink to request time slots from a base station. An example of this approach is the system disclosed in U.S. Pat. No. 5,638,371 assigned to NEC USA, Inc. The present invention eliminates the need for a base station to make slot assignments.
A number of protocols have been proposed in the recent past to provide dynamic time-slot allocation without requiring central base stations. These protocols can be classified as topology-independent and topology-dependent time scheduling protocols.
Shepard (T. Shepard, “A Channel Access Scheme for Large Dense Packet Radio Networks,” Proc. SIGCOMM '96, 1996; T. Shepard, “Scalable, Self-Configuring Packet Radio Network Having Decentralized Channel Management Providing Collision-Free Packet Transfer,” U.S. Pat. No. 5,682,382, Oct. 28, 1997), Chlamtac et al (I. Chlamtac et al, “Time-Spread Multiple-Access (TSMA) Protocols for Multihop Mobile Radio Networks,” IEEE/ACM Transactions on Networking, 'Vol. 5, no. 6, December 1997), and Ju and Li (Ji-Her Ju, Victor O. K. Li, “An Optimal Topology-Transparent Scheduling Method in Multihop Packet Radio Networks,” IEEE/ACM Transactions on Networking, Vol. 6, no. 3, June 1998) have proposed topology-independent time-scheduling protocols. In these protocols, nodes are pre-assigned (by means of their nodal IDs, for example) or adopt a transmission schedule that they publish, and such a schedule specifies the times when a node transmits and receives. The protocols guarantee or provide a high likelihood that at least one transmission time in a node's schedule does not conflict with any node one or two hops away. In the Chlamtac and Ju approaches, nodes are unable to determine which transmissions will succeed, complicating the job of higher layer (e.g., link-layer) protocols. These approaches also require values for the total number of nodes in the network and maximum number of neighbors for each node, as input parameters to the algorithm, thus making them design for the worst case conditions (and thus, inefficient if the network is not as dense as expected), or being sensitive to actual network conditions (if the network is larger or more dense than expected). Shepard's approach avoids collisions by assuming nodes are synchronized with their neighbors, have knowledge of their neighbors' schedules, and are able to receive from multiple transmitting neighbors simultaneously. This final assumption requires fairly sophisticated radio hardware.
Zhu and Corson (C. Zhu, M. S. Corson, “A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks,” Proc. IEEE INFOCOM '98) and Tang and Garcia-Luna-Aceves (Z. Tang and J. J. Garcia-Luna-Aceves, “A Protocol for Topology-Dependent Transmission Scheduling,” Proc. IEEE Wireless Communications and Networking Conference 1999 (WCNC 99), New Orleans, La., Sep. 21-24, 1999; Z. Tang and J. J. Garcia-Luna-Aceves, “Hop-Reservation Multiple Access (HRMA) for Multichannel Packet Radio Networks”, Proc. IEEE IC3N '98: Seventh International Conference on Computer Communications and Networks, Lafayette, La., Oct. 12-15, 1998) have developed topology-dependent scheduling protocols, such that a node acquires a transmission schedule that allows the node to transmit without interfering with nodes one and two hops away from itself, and such that channel reuse is increased as the number of neighbors per node decreases. These protocols require nodes to contend in order to reserve collision-free time slots, and the contention is done on each mini-slot. Furthermore, they rely on dividing each slot into several mini-slots. All this limits the minimum duration that slots may have. The present invention does not require slots to be subdivided, and does not require nodes to reply to neighbors in less than a frame time.
Several approaches have been proposed that are based on TDMA and require an initial, topology-independent schedule, followed by communication among the network nodes to negotiate a final schedule. Chlamtac (I. Chlamtac, “Fair Algorithms for Maximal Link Activation in Multihop Radio Networks,” IEEE Transactions on Communications, Vol. COM-35, no. 7, July, 1987) proposed an algorithm based on a repeating link schedule that can adapt to traffic demands after some number of iterations of the algorithm. The algorithm starts with a “single-slot-per-link” schedule, such as provided by assigning each node a transmission slot according to its node ID. At each iteration, schedule information and a scheduling “token” are routed up and down a routing tree (established by means of pre-existing algorithms), to assign additional slots to nodes or links according to their degree of unmet traffic demands. Ephremides and Truong (A. Ephremides, T. Truong, “Scheduling Broadcasts in Multihop Radio Networks,” IEEE Transactions on Communications, Vol. COM-38, No. 4, April, 1990) proposed a similar algorithm in which each node is initially assigned a slot corresponding to its node ID, and then each node uses their assignment to pass “skeleton” schedules to their neighbors. During the next two frames (two iterations of communicating schedules), and in accordance with fixed node priorities, nodes are able to grab available slots until all available slots are taken (i.e., no more slots can be assigned without causing collisions). Because of the need for schedules that are fixed, requiring a few iterations to converge, and of scheduling-frame size equal to the maximum size of the network, these approaches have limited scalability and robustness to mobility or other dynamics. The approach proposed by Young (C. D. Young, “USAP: A Unifying Dynamic Distributed Multichannel TDMA Slot Assignment Protocol,” Proc. IEEE MILCOM 96 OCTOBER 1996) also requires initial assignment of one slot per node, and then negotiation of scheduling packets for assignment of the other slots. However, the initially assigned slot is limited to the first slot in each “frame.” Thus, each node's assigned slot occurs every N frames, where N is the maximum network size. Because of this, the approach does not scale. Also, the approach is relatively slow in adapting to dynamic traffic conditions, because a node needs to wait up to N frames before a proposed schedule addition is confirmed by a neighbor.
The majority of the limitations described above for the MAC protocols in the prior art are eliminated with the Robust Environmentally Adaptive Link/MAC (REALM) protocol (D. Beyer, J. J. Garcia-Luna-Aceves, and C. Fullmer, “Adaptive Communication Protocol for Wireless Networks,” U.S. patent application Ser. No. 09/248,738, 10 Feb. 1999, in combination with the Neighborhood Established Transmission Scheduling (NETS) protocol (J. J. Garcia-Luna-Aceves, D. Beyer and C. Fullmer, “A Protocol for Neighborhood Established Transmission Scheduling,” application Ser. No. 09/418,899, 15 Oct. 1999).
REALM is a MAC protocol that achieves collision avoidance without the need for handshakes between senders and receivers. REALM assumes a synchronous network organized into time frames divided into slots. The amount of synchronization assumed in REALM is the same type of synchronization required in any network operating with frequency hopping radios, such as those designed to operate in ISM bands and commercially available today. A node running REALM must know the identities of its one-hop and two-hop neighbors and the present time in the network (e.g., the number of the current frame). Based on this information, and auxiliary information, each node evaluates a function (e.g., a hash function) that specifies deterministically which node should transmit in which time slot of a frame. REALM achieves fairness by changing in each frame the priority with which a given node can transmit in a time slot of the frame. Once all the nodes in the two-hop neighborhood of a node have consistent information regarding their neighborhood, collisions are avoided because all the nodes use the same deterministic algorithm to select a winner for a given time slot.
Bao and Garcia-Luna-Aceves (L. Bao and J. J. Garcia-Luna-Aceves, “A New Approach to Channel Access Scheduling for Ad Hoc Networks,” Proc. ACM MobiCom 2001—Seventh Annual International Conference on Mobile Computing and networking, Jul. 16-21, 2001, Rome, Italy; L. Bao and J. J. Garcia-Luna-Aceves, “Channel Access Scheduling in Ad Hoc Networks with Unidirectional Links,” Proc. ACM DialM 2001—Fifth International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Jul. 21, 2001 Rome, Italy; L. Bao and J. J. Garcia-Luna-Aceves, “A New Collision-Free Medium Access Control Protocol” Proc. IEEE MILCOM 2000, Los Angeles, Calif., Oct. 22-25, 2000.) have proposed channel access algorithms that achieve collision avoidance without the need for a specific handshake between sender and receiver in a way similar to REALM. These algorithms require each node to have the identifiers of all the nodes within two hops, and assign a transmission priority to a node during a given time slot based on this neighbor information. An unspecified algorithm is assumed to disseminate neighbor information.
A limitation of using REALM by itself, or the algorithms proposed by Bao and Garcia-Luna-Aceves, to transmit data packets into the channel is that these approaches make no bandwidth reservations to support traffic flows. Hence, the number of times a node is allowed to transmit in a fixed number of frames has no correlation with the number of data packets that need to flow through that node, which means that packets at the node can experience variable delays being queued at the node waiting to reach the channel.
To solve the above limitations, NETS is used in combination with REALM, or a similar collision-avoidance method, to send schedule packets during a control section of a frame. NETS consists of a distributed transmission scheduling protocol for ad-hoc networks that builds and maintains collision-free transfers of unicast, multicast and broadcast packets. NETS then uses a control method (e.g., REALM) to determine when the nodes of the computer network send their NETS schedule packets containing neighborhood information. All transmission schedules are built on demand in NETS. The basic approach adopted in NETS is that of an election of the best schedule reported by nodes within two hops of one another. NETS introduces a set of rules, called an etiquette, that allows all nodes to decide which the winning schedule is once all the nodes maintain consistent information about who their one- and two-hop neighbors are.
A limitation of NETS is that the bandwidth reservations made among nodes are established asynchronously and without the sources and destinations of the flows being able to control the bandwidth reservations over the links along the paths between them. This can lead to congestion at the destinations of traffic and those nodes required to forward traffic for many other nodes.
Therefore, there is a need in the industry for a mechanism for scheduling of transmissions without collisions in a network in which a router may move.